#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<ostream>
#include<ios>
#include<bits/locale_classes.h>
#include<bits/ios_base.h>
using namespace std;


class Solution{
    public:
    
    int str2int(string s){
        unordered_map<char, int> map = {
            {'0', 0},
            {'1', 1},
            {'2', 2},
            {'3', 3},
            {'4', 4},
            {'5', 5},
            {'6', 6},
            {'7', 7},
            {'8', 8},
            {'9', 9}
        };
        int ret = 0;
        if(s[0] == '-'){
            for(int i = 1; i != s.size(); i++){
                ret = ret * 10 + map[s[i]];
            }
            return -ret;
        }else{
            for(int i = 0; i != s.size(); i++){
                ret = ret * 10 + map[s[i]];
            }
            return ret;
        }
    }

    int ans1(vector<string>& tokens){
        stack<int> stk;
        
        for(int i = 0; i != tokens.size(); i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int num_back = stk.top();
                stk.pop();
                int num_front = stk.top();
                stk.pop();
                int temp;
                if(tokens[i] == "+"){
                    temp = num_front + num_back;
                }
                else if(tokens[i] == "-"){
                    temp = num_front - num_back;
                }
                else if(tokens[i] == "*"){
                    temp = num_front * num_back;
                }
                else{
                    temp = num_front / num_back;
                }
                stk.push(temp);
                
            }else{
                // stk.push(str2int(tokens[i]));
                stk.push(atoi(tokens[i].c_str()));
            }
        }
        return stk.top();
    }
};

void test1(){
    Solution s;
    vector<string> str = {"2","1","+","3","*"};
    int ret = s.ans1(str);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<string> str = {"-78","-33","196","+","-19","-","115","+","-","-99","/","-18","8","*","-86","-","-","16","/","26","-14","-","-","47","-","101","-","163","*","143","-","0","-","171","+","120","*","-60","+","156","/","173","/","-24","11","+","21","/","*","44","*","180","70","-40","-","*","86","132","-84","+","*","-","38","/","/","21","28","/","+","83","/","-31","156","-","+","28","/","95","-","120","+","8","*","90","-","-94","*","-73","/","-62","/","93","*","196","-","-59","+","187","-","143","/","-79","-89","+","-"};
    int ret = s.ans1(str);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<string> str = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    int ret = s.ans1(str);
    cout << ret << endl;
}


int main(void){
    test1();
    test2();
    test3();

    return 0;
}